import java.util.*;

/**
 * @author SaoE
 * @date 2025/3/2 19:03
 */
public class _279 {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++){
            dp[i] = 999;
            // if (isSquare(i)){
            //     dp[i] = 1;
            // }
            for (int j = 1; i - j * j >= 0; j++){
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }
    public boolean isSquare(int num){
        for (int i = 1; i < num / 2 + 1; i++){
            if (i * i == num){
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Map<Integer, Integer> map = new HashMap<>();
        List<Integer> list = new ArrayList<>();

    }
}
